The subject matter discussed in the background section should not be assumed to be prior art merely as a result of its mention in the background section. Similarly, a problem mentioned in the background section or associated with the subject matter of the background section should not be assumed to have been previously recognized in the prior art. The subject matter in the background section merely represents different approaches, which in and of themselves may also correspond to implementations of the claimed technology.
In the realm of distributed computing, overall system operation can be greatly impacted one way or the other by the decisions about which computations are carried out on which compute resources. Optimizing the distribution of work is a type of scheduling problem: some logic mechanism decides when to compute what, where, when and for how long. Traditionally such scheduling use deterministic rules arrived at by study and experimentation, but these typically only achieve optimal utilization of compute resources when the compute resources are homogeneous, and often only when the computations are as well. As used herein, in the context of an environment comprising compute resources for assigning computation, “homogeneous” means that each compute resource is identical to the others in use, in terms of configuration, capability, capacity, and availability. How effectively a distributed computing scheduler assigns work to compute resources determines in large part the financial costs associated with those computations. In a homogeneous computing environment one may determine the optimal schedule to execute a distributed program a priori as a straightforward set of calculations.
Scheduling heterogeneous computations on a set of heterogeneous compute resources is an active area of research, where the differences between compute resources include, but are not limited to: availability, computational power (clock frequency, number of cores, cache sizes, etc.), available volatile storage (memory), available persistent storage (disk), bandwidth for inter-process communications and data transfer, various forms of latency, time to load data, etc. In such an environment the costs to execute a distributable program can vary significantly based on which compute resource is selected. This scheduling problem is further complicated when the compute resources and communications with and between them have time varying performance and prices, depending on external factors such as market forces (e.g., supply and demand), and environmental conditions (e.g., network performance and reliability in different parts of the world.)
In such a heterogeneous distributed computing environment, determining the optimal scheduling of work among a set of such compute resources is a combinatorial problem of enormous size and complexity, for which there does not exist a closed form or effective heuristic solution: this problem is generally accepted to be NP-Hard.